package arithmetic;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

import utils.TreeNode;


/**
 * Created by jiangfeng on 2017/9/29. //二叉树的遍历： 非递归遍历
 *
 */
public class BinTree {

  

    /**
     * 测试用例:
     *       1
     *      / \
     *     2   3
     *    /\   /\
     *  4  5  6  7
     *            \
     *             8
     * @param args
     */
    public static void main(String[] args) {
        TreeNode TreeNode4 = new TreeNode(4);
        TreeNode TreeNode5 = new TreeNode(5);
        TreeNode TreeNode6 = new TreeNode(6);
        TreeNode TreeNode7 = new TreeNode(7);
        TreeNode TreeNode1 = new TreeNode(1);
        TreeNode TreeNode2 = new TreeNode(2);
        TreeNode TreeNode3 = new TreeNode(3);
        TreeNode TreeNode8 = new TreeNode(8);
        TreeNode7.right=TreeNode8;
        TreeNode2.left = TreeNode4;
        TreeNode2.right = TreeNode5;
        TreeNode3.left = TreeNode6;
        TreeNode3.right = TreeNode7;
        TreeNode1.left = TreeNode2;
        TreeNode1.right = TreeNode3;

        String s = serialize1(TreeNode1);
        printTree(TreeNode1);
        System.out.println(s);
        TreeNode deserialize = derialize1(s);

        String serialize = serialize(deserialize);
        System.out.println(serialize);
       // 非递归中序
        System.out.println("非递归中序:"+serializeNoCenter(deserialize));
        // 后序遍历
        System.out.println(serializeNoBack(deserialize));
        // 层次遍历
        String serializeLevel = serializeLevel(deserialize);
        System.out.println("层次:"+ serializeLevel);
        TreeNode derializeLevel = derializeLevel(serializeLevel);
        System.out.println(derializeLevel);
    }

    public static  TreeNode derializeLevel(String data){
        if(data == null|| data.length()==0) {
            return null;
        }
        String[] split = data.split(",");

        Queue<TreeNode> queue = new LinkedList<>();
        int index =0;
        TreeNode head = new TreeNode(Integer.valueOf(split[index++]));
        queue.add(head);

        while(!queue.isEmpty()){
            TreeNode poll = queue.poll();
            poll.left = genTreeNode(split[index++]);
            if(poll.left!=null){
                queue.add(poll.left);
            }
            poll.right = genTreeNode(split[index++]);
            if(poll.right!=null){
                queue.add(poll.right);
            }
        }
        return head;
        /*for (int i = 0; i < split.length; i++) {
            String s = split[i];
            TreeNode bin = (s == null || s.equals("#")) ? null : new TreeNode(Integer.valueOf(s));
        }*/

    }

    // 层序遍历打印
    public static void printTree(TreeNode root){
        final String nul = "#";
        if(root==null){
            return;
        }
        Deque<TreeNode> dq = new LinkedList<>();
        dq.offer(root);
        while (!dq.isEmpty()){
            List<String> list = new ArrayList<>();
            int size = dq.size();
            while(size>0){
                // 最后一个开始打印。
                TreeNode node = dq.poll();
                list.add(node==null?nul:String.valueOf(node.val));
                if(node!=null){
                    dq.offer(node.left);
                    dq.offer(node.right);
                }
                if(size==1){
                    System.out.println(list);
                    list = new ArrayList<>();
                }
                size--;
            }

        }
    }
    public static TreeNode genTreeNode(String node){
        if(node == null || node.equals("#")){
            return  null;
        }
        return new TreeNode(Integer.valueOf(node));
    }

    /**
     * 层次遍历
     * @param root
     * @return
     */
    public static String serializeLevel(TreeNode root){
        final String split = ",";
        final String nul = "#";
        if (root == null) {
            return split+nul;
        }
        StringBuilder result = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        result.append(root.val).append(split);
        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            if (poll == null) {
                continue;
            }
            TreeNode left = poll.left;
            TreeNode right = poll.right;
            result.append(left == null ? nul : left.val).append(split);
            result.append(right == null ? nul : right.val).append(split);
            queue.add(left);
            queue.add(right);
        }
        return result.toString();
    }

    // 非递归版,后续遍历.
    public static String serializeNoBack(TreeNode root){
        final String split = ",";
        final String nul = "#";
        if (root == null) {
            return split+nul;
        }
        StringBuilder result = new StringBuilder();
        Stack<TreeNode> st = new Stack<>();
        TreeNode index= root;
        while (index != null || !st.isEmpty()) {
            if (index != null) {
                st.push(index);
                index = index.left;
            } else {
                TreeNode pop = st.pop();
                index = pop.right;
            }
        }
        return result.toString();
    }

    // 非递归版 recursion, 中序遍历
    public static String serializeNoCenter(TreeNode root){
        final String split = ",";
        final String nul = "#";
        if (root == null) {
            return split+nul;
        }
        StringBuilder result = new StringBuilder();
        Stack<TreeNode> st = new Stack<>();
        TreeNode index= root;
        while (index != null || !st.isEmpty()) {
            if (index != null) {
                st.push(index);
                //result.append(index.value).append(split);
                index = index.left;
            } else {
                result.append(nul).append(split);
                TreeNode pop = st.pop();
                result.append(pop.val).append(split);
                index = pop.right;
            }
        }
        return result.toString();
    }


    // 递归版 recursion, 前序遍历
    public static String serialize1(TreeNode root){
        if(root==null){
            return "#,";
        }
        String result = "";
        result+=root.val+",";
        result+=serialize1(root.left);
        result+=serialize1(root.right);
        return result;
    }
    public static TreeNode derialize1(String data){
       if(data == null|| data.length()==0) {
           return null;
       }
        return derialize1_(data.split(","));
    }

    public static int  index = -1;

    public static TreeNode derialize1_(String[] datas){
        index++;
        String datum = datas[index];
        if(datum == null|| datum.length()==0|| "#".equals(datum)) {
            return null;
        }
        TreeNode result = new TreeNode(Integer.valueOf(datum));
        result.left= derialize1_(datas);
        result.right= derialize1_(datas);
        return  result;
    }

    // Encodes a tree to a single string.
    // 非递归版,前序遍历
    public static String serialize(TreeNode root) {
        final String split = ",";
        final String nul = "#";
        String[] split1 = nul.split(split);
        //StringBuilder sb = new StringBuilder();
        // 前序遍历
        if (root == null) {
            return split+nul;
        }
        StringBuilder result = new StringBuilder();
        Stack<TreeNode> st = new Stack<>();
        TreeNode index= root;
        while (index != null || !st.isEmpty()) {
            result.append(index==null?nul:index.val).append(split);
            if (index != null) {
                st.push(index);
                index = index.left;
            } else {
                index = st.pop().right;

            }
        }
        return result.toString();
    }
   /* public static TreeNode getLeft(TreeNode root,Stack<TreeNode> st,String re){
        TreeNode left= root.left;
        while (left != null) {
            st.push(left);
            result.add(left.value);
            left = left.left;
        }
    }*/


    // Decodes your encoded data to tree.
    public static TreeNode deserialize(String data) {
        return null;
    }




    /**
     * @param node 二叉树的节点
     * @param deep int[0] 存取改子树深度 int[1]存取该子树的最远距离
     * 二叉树任意两节点的最远距离 思路： 1.任意节点的深度=左右子树中较大的加1 2.最远距离可能是经过跟节点：此时距离为 左右深度之和，也可能不经过根节点，那就算该字数的最远距离
     *
     */
    public static void findMaxdis(TreeNode node, int[] deep) {
        if (node == null) {
            deep[0] = 0;
            deep[1] = 0;
            return;
        }
        int[] l_deep = new int[2], r_deep = new int[2];
        if (null != node.left) {
            findMaxdis(node.left, l_deep);
        }
        if (null != node.right) {
            findMaxdis(node.right, r_deep);
        }
        deep[0] = (l_deep[0] > r_deep[0] ? l_deep[0] : r_deep[0]) + 1;
        deep[1] = l_deep[1] > r_deep[1] ? l_deep[1] : r_deep[1];
        deep[1] = (l_deep[0] + r_deep[0]) > deep[1] ? (l_deep[0] + r_deep[0]) : deep[1];
    }

    public static int findMaxDis(TreeNode node) {
        int[] deep = new int[2];
        findMaxdis(node, deep);
        return deep[1];
    }


}
